In digital communication, transmission of information sometimes produces error. Techniques of reducing and monitoring error have been developed. Error can be monitored and sometimes corrected. One area that has developed has centered around Hamming codes, and particularly shortened Hamming codes.
Hamming codes introduce redundancy in data by adding information to existing data to identify and correct error following transmission of the data. For example, appending an error correction code to a unit of data and transmitting the resulting codeword can allow for higher tolerance to noise and error.
Typically, a transmitter encodes a data unit to produce what is sometimes referred to as a “codeword.” The transmitter then sends the codeword to a receiver. Typically, a receiver decodes the codeword to obtain the original data unit and the error correction code. A decoder in the receiver may include a trellis representation of a Hamming code. A trellis representation is a view of a convolutional or block code explained using a trellis diagram.
In drawing a trellis, sets of states are used to represent all possible points which can be assumed at successive stages by a state machine, which is used to encode source data. Before sending, data is encoded into a codeword from a limited number of possible codewords including error correction data. Only a specific set of codewords is permitted for transmission. Upon receipt, a receiver implementing a trellis decoder decodes the codewords and provides the data to a communications system.
Once a codeword has been properly received, a trellis search algorithm, such as the Viterbi algorithm or the Bahl, Cocke, Jelinek, Raviv (BCJR) algorithm, can be used to decode the codeword. Notably, there is a large number of computational steps required to perform Viterbi or other trellis decoding. The complexity of a decoder based on the Viterbi or other trellis search algorithms may increase in complexity based on the size of the trellis structure corresponding to the decoder. The number of computational steps required to perform Viterbi or other trellis search decoding is related to the size of the trellis structure used to implement the decoder.